#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int dp(vector<vector<int>>& tb, vector<vector<int>> &bak, int n, int m)
{
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        dp[i][j] = dp[i - 1][j];
                        bak[i][j] = 0;
                        for(int k = 1; k <= j; k++){
                                int cur_val = dp[i -1][j - k] + tb[i][k];
                                if(cur_val >= dp[i][j]) {
                                        dp[i][j] = cur_val;
                                        bak[i][j] = k;
                                }
                        }
                }
        }
        return dp[n][m];
}

int recur(vector<vector<int>>& tb, vector<vector<int>> &rec, vector<vector<int>> &bak, int n, int m)
{
        if(n == 0 || m == 0) return 0;
        if(rec[n][m] != 0) return rec[n][m];
        
        bak[n][m] = 0; // Initialize the bak array for the current row
        int max_val = recur(tb, rec, bak, n - 1, m);
        for(int k = 1; k <= m; k++){
                int cur_val = recur(tb, rec, bak, n - 1, m - k) + tb[n][k];
                if(cur_val >= max_val) {
                        max_val = cur_val;
                        rec[n][m] = max_val;
                        bak[n][m] = k;
                }
        }
        return max_val;
}

int main()
{
        int n, m;
        cin >> n >> m;
        vector<vector<int>> tb(n + 1, vector<int>(m + 1, 0));
        vector<vector<int>> bak(tb);

        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        cin >> tb[i][j];
                }
        }
        
        vector<vector<int>> rec(n + 1, vector<int>(m + 1, 0));
        vector<int> ans;
        //cout<<dp(tb, bak, n, m) << endl;
        cout<<recur(tb, rec, bak, n, m) << endl;
        for(int i = n; i >= 1; i--){
                ans.push_back(bak[i][m]);
                m -= bak[i][m];
        }
        reverse(ans.begin(), ans.end());
        for(int i = 0; i < ans.size(); i++){
                cout << i +1  << " "<<ans[i] << endl;
        }   
        return 0;
}
/*
3 3
30 40 50
20 30 50
20 25 30
*/